#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VERTEX_NUM 100
#define INFINITY 32768  // 表示无穷大

// 顶点数据类型定义
typedef char VertexData;

// 邻接矩阵结构定义
typedef struct {
	VertexData vertex[MAX_VERTEX_NUM];  // 顶点数组
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵
	int vertexnum, arcnum;  // 顶点数和弧数/边数
} AdjMatrix;

// 邻接表边表节点定义
typedef struct ArcNode {
	int adjvex;  // 邻接点在顶点数组中的下标
	int weight;  // 边的权值
	struct ArcNode *next;  // 下一条边指针
} ArcNode;

// 邻接表顶点表节点定义
typedef struct VertexNode {
	VertexData data;  // 顶点数据
	ArcNode *first;  // 指向第一条边
} VertexNode;

// 邻接表结构定义
typedef struct {
	VertexNode vertices[MAX_VERTEX_NUM];  // 顶点表
	int vertexnum, arcnum;  // 顶点数和弧数/边数
} AdjList;

// 在邻接矩阵中查找顶点下标
int LocateVertex(AdjMatrix *G, VertexData v) {
	int k;
	for (k = 0; k < G->vertexnum; k++) {
		if (G->vertex[k] == v) {
			return k;
		}
	}
	return -1;
}

// 在邻接表中查找顶点下标
int LocateVertex_AL(AdjList *G, VertexData v) {
	int k;
	for (k = 0; k < G->vertexnum; k++) {
		if (G->vertices[k].data == v) {
			return k;
		}
	}
	return -1;
}

// 创建有向网(邻接矩阵)
int CreateDN_M(AdjMatrix *G) {
	int i, j, k, weight;
	VertexData v1, v2;
	
	printf("输入有向网的顶点数和弧数，以逗号分隔: ");
	scanf("%d,%d", &G->vertexnum, &G->arcnum);
	
	// 初始化邻接矩阵
	for (i = 0; i < G->vertexnum; i++) {
		for (j = 0; j < G->vertexnum; j++) {
			if (i == j)
				G->arcs[i][j] = 0;
			else
				G->arcs[i][j] = INFINITY;
		}
	}
	
	printf("输入%d个顶点信息(单个字符): ", G->vertexnum);
	getchar();
	for (i = 0; i < G->vertexnum; i++) {
		scanf("%c", &G->vertex[i]);
	}
	
	printf("输入%d条弧的信息(起点 终点 权值):\n", G->arcnum);
	for (k = 0; k < G->arcnum; k++) {
		printf("第%d条弧: ", k + 1);
		scanf(" %c %c %d", &v1, &v2, &weight);
		i = LocateVertex(G, v1);
		j = LocateVertex(G, v2);
		if (i != -1 && j != -1) {
			G->arcs[i][j] = weight;
		} else {
			printf("顶点不存在，弧创建失败！\n");
			k--;
		}
	}
	return 1;
}

// 创建无向网(邻接矩阵)
int CreateUN_M(AdjMatrix *G) {
	int i, j, k, weight;
	VertexData v1, v2;
	
	printf("输入无向网的顶点数和边数，以逗号分隔: ");
	scanf("%d,%d", &G->vertexnum, &G->arcnum);
	
	// 初始化邻接矩阵
	for (i = 0; i < G->vertexnum; i++) {
		for (j = 0; j < G->vertexnum; j++) {
			if (i == j)
				G->arcs[i][j] = 0;
			else
				G->arcs[i][j] = INFINITY;
		}
	}
	
	printf("输入%d个顶点信息(单个字符): ", G->vertexnum);
	getchar();
	for (i = 0; i < G->vertexnum; i++) {
		scanf("%c", &G->vertex[i]);
	}
	
	printf("输入%d条边的信息(顶点1 顶点2 权值):\n", G->arcnum);
	for (k = 0; k < G->arcnum; k++) {
		printf("第%d条边: ", k + 1);
		scanf(" %c %c %d", &v1, &v2, &weight);
		i = LocateVertex(G, v1);
		j = LocateVertex(G, v2);
		if (i != -1 && j != -1) {
			G->arcs[i][j] = weight;
			G->arcs[j][i] = weight;  // 无向网对称赋值
		} else {
			printf("顶点不存在，边创建失败！\n");
			k--;
		}
	}
	return 1;
}

// 创建有向图(邻接矩阵)
int CreateDG_M(AdjMatrix *G) {
	int i, j, k;
	VertexData v1, v2;
	
	printf("输入有向图的顶点数和弧数，以逗号分隔: ");
	scanf("%d,%d", &G->vertexnum, &G->arcnum);
	
	// 初始化邻接矩阵
	for (i = 0; i < G->vertexnum; i++) {
		for (j = 0; j < G->vertexnum; j++) {
			G->arcs[i][j] = 0;
		}
	}
	
	printf("输入%d个顶点信息(单个字符): ", G->vertexnum);
	getchar();
	for (i = 0; i < G->vertexnum; i++) {
		scanf("%c", &G->vertex[i]);
	}
	
	printf("输入%d条弧的信息(起点 终点):\n", G->arcnum);
	for (k = 0; k < G->arcnum; k++) {
		printf("第%d条弧: ", k + 1);
		scanf(" %c %c", &v1, &v2);
		i = LocateVertex(G, v1);
		j = LocateVertex(G, v2);
		if (i != -1 && j != -1) {
			G->arcs[i][j] = 1;  // 有向图边权为1
		} else {
			printf("顶点不存在，弧创建失败！\n");
			k--;
		}
	}
	return 1;
}

// 创建无向图(邻接矩阵)
int CreateUG_M(AdjMatrix *G) {
	int i, j, k;
	VertexData v1, v2;
	
	printf("输入无向图的顶点数和边数，以逗号分隔: ");
	scanf("%d,%d", &G->vertexnum, &G->arcnum);
	
	// 初始化邻接矩阵
	for (i = 0; i < G->vertexnum; i++) {
		for (j = 0; j < G->vertexnum; j++) {
			G->arcs[i][j] = 0;
		}
	}
	
	printf("输入%d个顶点信息(单个字符): ", G->vertexnum);
	getchar();
	for (i = 0; i < G->vertexnum; i++) {
		scanf("%c", &G->vertex[i]);
	}
	
	printf("输入%d条边的信息(顶点1 顶点2):\n", G->arcnum);
	for (k = 0; k < G->arcnum; k++) {
		printf("第%d条边: ", k + 1);
		scanf(" %c %c", &v1, &v2);
		i = LocateVertex(G, v1);
		j = LocateVertex(G, v2);
		if (i != -1 && j != -1) {
			G->arcs[i][j] = 1;  // 无向图边权为1
			G->arcs[j][i] = 1;  // 无向图对称赋值
		} else {
			printf("顶点不存在，边创建失败！\n");
			k--;
		}
	}
	return 1;
}

// 输出邻接矩阵
void OutPutGraph_M(AdjMatrix G) {
	int i, j;
	printf("\n邻接矩阵表示:\n");
	printf("  ");
	for (i = 0; i < G.vertexnum; i++) {
		printf("%c ", G.vertex[i]);
	}
	printf("\n");
	
	for (i = 0; i < G.vertexnum; i++) {
		printf("%c ", G.vertex[i]);
		for (j = 0; j < G.vertexnum; j++) {
			if (G.arcs[i][j] == INFINITY)
				printf("∞ ");
			else
				printf("%d ", G.arcs[i][j]);
		}
		printf("\n");
	}
}

// 创建有向网(邻接表)
int CreateDN_AL(AdjList *G) {
	int i, j, k, weight;
	VertexData v1, v2;
	ArcNode *newArc;
	
	printf("输入有向网的顶点数和弧数，以逗号分隔: ");
	scanf("%d,%d", &G->vertexnum, &G->arcnum);
	
	// 初始化顶点表
	printf("输入%d个顶点信息(单个字符): ", G->vertexnum);
	getchar();
	for (i = 0; i < G->vertexnum; i++) {
		scanf("%c", &G->vertices[i].data);
		G->vertices[i].first = NULL;  // 边表初始为空
	}
	
	printf("输入%d条弧的信息(起点 终点 权值):\n", G->arcnum);
	for (k = 0; k < G->arcnum; k++) {
		printf("第%d条弧: ", k + 1);
		scanf(" %c %c %d", &v1, &v2, &weight);
		i = LocateVertex_AL(G, v1);
		j = LocateVertex_AL(G, v2);
		
		if (i != -1 && j != -1) {
			// 创建新边节点
			newArc = (ArcNode *)malloc(sizeof(ArcNode));
			if (!newArc) {
				printf("内存分配失败！\n");
				return 0;
			}
			newArc->adjvex = j;
			newArc->weight = weight;
			
			// 头插法插入边表
			newArc->next = G->vertices[i].first;
			G->vertices[i].first = newArc;
		} else {
			printf("顶点不存在，弧创建失败！\n");
			k--;
		}
	}
	return 1;
}

// 创建无向网(邻接表)
int CreateUN_AL(AdjList *G) {
	int i, j, k, weight;
	VertexData v1, v2;
	ArcNode *newArc1, *newArc2;
	
	printf("输入无向网的顶点数和边数，以逗号分隔: ");
	scanf("%d,%d", &G->vertexnum, &G->arcnum);
	
	// 初始化顶点表
	printf("输入%d个顶点信息(单个字符): ", G->vertexnum);
	getchar();
	for (i = 0; i < G->vertexnum; i++) {
		scanf("%c", &G->vertices[i].data);
		G->vertices[i].first = NULL;  // 边表初始为空
	}
	
	printf("输入%d条边的信息(顶点1 顶点2 权值):\n", G->arcnum);
	for (k = 0; k < G->arcnum; k++) {
		printf("第%d条边: ", k + 1);
		scanf(" %c %c %d", &v1, &v2, &weight);
		i = LocateVertex_AL(G, v1);
		j = LocateVertex_AL(G, v2);
		
		if (i != -1 && j != -1) {
			// 创建两条边(无向图边是双向的)
			// 边v1->v2
			newArc1 = (ArcNode *)malloc(sizeof(ArcNode));
			if (!newArc1) {
				printf("内存分配失败！\n");
				return 0;
			}
			newArc1->adjvex = j;
			newArc1->weight = weight;
			newArc1->next = G->vertices[i].first;
			G->vertices[i].first = newArc1;
			
			// 边v2->v1
			newArc2 = (ArcNode *)malloc(sizeof(ArcNode));
			if (!newArc2) {
				printf("内存分配失败！\n");
				return 0;
			}
			newArc2->adjvex = i;
			newArc2->weight = weight;
			newArc2->next = G->vertices[j].first;
			G->vertices[j].first = newArc2;
		} else {
			printf("顶点不存在，边创建失败！\n");
			k--;
		}
	}
	return 1;
}

// 创建有向图(邻接表)
int CreateDG_AL(AdjList *G) {
	int i, j, k;
	VertexData v1, v2;
	ArcNode *newArc;
	
	printf("输入有向图的顶点数和弧数，以逗号分隔: ");
	scanf("%d,%d", &G->vertexnum, &G->arcnum);
	
	// 初始化顶点表
	printf("输入%d个顶点信息(单个字符): ", G->vertexnum);
	getchar();
	for (i = 0; i < G->vertexnum; i++) {
		scanf("%c", &G->vertices[i].data);
		G->vertices[i].first = NULL;  // 边表初始为空
	}
	
	printf("输入%d条弧的信息(起点 终点):\n", G->arcnum);
	for (k = 0; k < G->arcnum; k++) {
		printf("第%d条弧: ", k + 1);
		scanf(" %c %c", &v1, &v2);
		i = LocateVertex_AL(G, v1);
		j = LocateVertex_AL(G, v2);
		
		if (i != -1 && j != -1) {
			// 创建新边节点(权值默认为1)
			newArc = (ArcNode *)malloc(sizeof(ArcNode));
			if (!newArc) {
				printf("内存分配失败！\n");
				return 0;
			}
			newArc->adjvex = j;
			newArc->weight = 1;
			
			// 头插法插入边表
			newArc->next = G->vertices[i].first;
			G->vertices[i].first = newArc;
		} else {
			printf("顶点不存在，弧创建失败！\n");
			k--;
		}
	}
	return 1;
}

// 创建无向图(邻接表)
int CreateUG_AL(AdjList *G) {
	int i, j, k;
	VertexData v1, v2;
	ArcNode *newArc1, *newArc2;
	
	printf("输入无向图的顶点数和边数，以逗号分隔: ");
	scanf("%d,%d", &G->vertexnum, &G->arcnum);
	
	// 初始化顶点表
	printf("输入%d个顶点信息(单个字符): ", G->vertexnum);
	getchar();
	for (i = 0; i < G->vertexnum; i++) {
		scanf("%c", &G->vertices[i].data);
		G->vertices[i].first = NULL;  // 边表初始为空
	}
	
	printf("输入%d条边的信息(顶点1 顶点2):\n", G->arcnum);
	for (k = 0; k < G->arcnum; k++) {
		printf("第%d条边: ", k + 1);
		scanf(" %c %c", &v1, &v2);
		i = LocateVertex_AL(G, v1);
		j = LocateVertex_AL(G, v2);
		
		if (i != -1 && j != -1) {
			// 创建两条边(无向图边是双向的，权值默认为1)
			// 边v1->v2
			newArc1 = (ArcNode *)malloc(sizeof(ArcNode));
			if (!newArc1) {
				printf("内存分配失败！\n");
				return 0;
			}
			newArc1->adjvex = j;
			newArc1->weight = 1;
			newArc1->next = G->vertices[i].first;
			G->vertices[i].first = newArc1;
			
			// 边v2->v1
			newArc2 = (ArcNode *)malloc(sizeof(ArcNode));
			if (!newArc2) {
				printf("内存分配失败！\n");
				return 0;
			}
			newArc2->adjvex = i;
			newArc2->weight = 1;
			newArc2->next = G->vertices[j].first;
			G->vertices[j].first = newArc2;
		} else {
			printf("顶点不存在，边创建失败！\n");
			k--;
		}
	}
	return 1;
}

// 输出邻接表
void OutPutGraph_AL(AdjList G) {
	int i;
	ArcNode *p;
	printf("\n邻接表表示:\n");
	for (i = 0; i < G.vertexnum; i++) {
		printf("%c -> ", G.vertices[i].data);
		p = G.vertices[i].first;
		while (p) {
			printf("(%c, %d) ", G.vertices[p->adjvex].data, p->weight);
			p = p->next;
		}
		printf("\n");
	}
}

// 释放邻接表内存
void FreeAdjList(AdjList *G) {
	int i;
	ArcNode *p, *q;
	for (i = 0; i < G->vertexnum; i++) {
		p = G->vertices[i].first;
		while (p) {
			q = p;
			p = p->next;
			free(q);
		}
	}
}

// 主菜单
void ShowMenu() {
	printf("\n请选择你实现想要的操作：\n");
	printf("1. 创建有向网(邻接矩阵)\n");
	printf("2. 创建无向网(邻接矩阵)\n");
	printf("3. 创建有向图(邻接矩阵)\n");
	printf("4. 创建无向图(邻接矩阵)\n");
	printf("5. 创建有向网(邻接表)\n");
	printf("6. 创建无向网(邻接表)\n");
	printf("7. 创建有向图(邻接表)\n");
	printf("8. 创建无向图(邻接表)\n");
	printf("0. 退出程序\n");
	printf("请输入选项(0-8): ");
}

int main() {
	int choice;
	AdjMatrix M_G;
	AdjList AL_G;
	
	while (1) {
		ShowMenu();
		scanf("%d", &choice);
		
		switch (choice) {
		case 0:
			printf("程序已退出，再见！\n");
			return 0;
			
		case 1:
			// 初始化邻接矩阵
			memset(&M_G, 0, sizeof(AdjMatrix));
			if (CreateDN_M(&M_G)) {
				OutPutGraph_M(M_G);
			}
			break;
			
		case 2:
			memset(&M_G, 0, sizeof(AdjMatrix));
			if (CreateUN_M(&M_G)) {
				OutPutGraph_M(M_G);
			}
			break;
			
		case 3:
			memset(&M_G, 0, sizeof(AdjMatrix));
			if (CreateDG_M(&M_G)) {
				OutPutGraph_M(M_G);
			}
			break;
			
		case 4:
			memset(&M_G, 0, sizeof(AdjMatrix));
			if (CreateUG_M(&M_G)) {
				OutPutGraph_M(M_G);
			}
			break;
			
		case 5:
			// 初始化邻接表
			memset(&AL_G, 0, sizeof(AdjList));
			if (CreateDN_AL(&AL_G)) {
				OutPutGraph_AL(AL_G);
				// 释放内存
				FreeAdjList(&AL_G);
			}
			break;
			
		case 6:
			memset(&AL_G, 0, sizeof(AdjList));
			if (CreateUN_AL(&AL_G)) {
				OutPutGraph_AL(AL_G);
				FreeAdjList(&AL_G);
			}
			break;
			
		case 7:
			memset(&AL_G, 0, sizeof(AdjList));
			if (CreateDG_AL(&AL_G)) {
				OutPutGraph_AL(AL_G);
				FreeAdjList(&AL_G);
			}
			break;
			
		case 8:
			memset(&AL_G, 0, sizeof(AdjList));
			if (CreateUG_AL(&AL_G)) {
				OutPutGraph_AL(AL_G);
				FreeAdjList(&AL_G);
			}
			break;
			
		default:
			printf("无效选项，请重新输入！\n");
		}
	}
	
	return 0;
}
